package org.example.Sort;

import org.example.Example.Marge;
import org.example.Tool.Tool;

import java.util.Arrays;
/**
 * <pre>
 * name 快速排序
 * time O(NlogN)
 * space O(NlogN)
 * @see Marge
 * @author 荷兰国旗问题
 * </pre>
 * */
public class FastSort extends Tool {
    public void sort(int[] arr){
        process(arr,0,arr.length-1);
    }
    private void process(int[] arr, int L, int R){
        if(L<R) {
            swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
            int[] marge = marge(arr, L, R);
            process(arr, L, marge[0] - 1);
            process(arr, marge[1] + 1, R);
        }

    }
    private int[] marge(int [] arr,int L,int R){
        int left=L-1;
        int right = R;

        while(L<right){
            if(arr[L]<arr[R]){
                swap(arr,++left,L++);
            }
            else if(arr[L]>arr[R]){
                swap(arr,--right,L);
            }
            else
                L++;
        }
        swap(arr,right,R);
        return new int[]{left+1,right};
    }

    public static void main(String[] args) {
        int[] arr = {2,61,32,1,6551,212,650,651126,6,0,0};
        new FastSort().sort(arr);
        Arrays.stream(arr).forEach(System.out::println);
    }
}
